package com.longge;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;

/**
 * @program: my-code
 * @description:
 * @author: longge
 * @create: 2021-05-03 00:52
 */
public class OpenLock {
    public int openLock(String[] deadends, String target) {
        LinkedList<String> queue = new LinkedList<>();
        queue.add("0000");
        HashSet<String> visited = new HashSet<>(Arrays.asList(deadends));
        boolean b = visited.add("0000");
        if (!b) return -1;
        int count = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String str = queue.poll();
                if (str.equals(target)) return count;
                for (int j = 0; j < 4; j++) {
                    String plus = plusStr(str, j);
                    if (!visited.contains(plus)) {
                        visited.add(plus);
                        queue.offer(plus);

                    };
                    String subtract = subStr(str, j);
                    if (!visited.contains(subtract)) {
                        visited.add(subtract);
                        queue.offer(subtract);

                    }
                }
            }
            count++;
        }
        return -1;
    }

    private String subStr(String str, int i) {
        char[] chars = str.toCharArray();
        if (chars[i] == '0') chars[i]='9';
        else chars[i] -= 1;
        StringBuilder sb = new StringBuilder();
        for (char aChar : chars) {
            sb.append(aChar);
        }
        return sb.toString();
    }

    private String plusStr(String str, int i) {

        char[] chars = str.toCharArray();
        if (chars[i] == '9') chars[i]='0';
        else chars[i] += 1;
        StringBuilder sb = new StringBuilder();
        for (char aChar : chars) {
            sb.append(aChar);
        }
        return sb.toString();
    }


}
